package com.faiz.algorithm;

import java.util.HashMap;
import java.util.Map;

public class MinWindow {
    // 滑动窗口算法
    public String minWindow(String s, String t) {
        // 初始化条件和窗口hash
        Map<Character, Integer> needs = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        String res = null;
        for (char c : t.toCharArray()) {
            needs.computeIfPresent(c, (key, value) -> value + 1);
            needs.computeIfAbsent(c, key -> 1);
        }
        // 滑动窗口算法主体
        int left = 0, right = 0;
        char[] chars = s.toCharArray();

        while (right < chars.length) {
            char cur = chars[right];
            right++;
            changeValueInWindow(needs, window, cur, true);
            // 满足条件的情况下进行优化
            while (isSatisfyTheNeeds(needs, window)) {
                // 需要移除的字符
                char del = chars[left];

                changeValueInWindow(needs, window, del, false);
                if (res == null) {
                    res = s.substring(left, right);
                } else {
                    String tmp = s.substring(left, right);

                    if (tmp.length() < res.length()) {
                        res = tmp;
                    }
                }
                left++;
            }
        }

        return res == null ? "" : res;
    }
    // 改变窗口中的值(add表示添加值)
    private void changeValueInWindow(Map<Character, Integer> needs, Map<Character, Integer> window, char c, boolean add) {
        if (needs.containsKey(c)) {
            if (add) {
                window.computeIfPresent(c, (key, value) -> value + 1);
                window.computeIfAbsent(c, key -> 1);
            } else {
                window.computeIfPresent(c, (key, value) -> value - 1);
            }
        }
    }

    // 判断当前的窗口是否已经满足条件
    private boolean isSatisfyTheNeeds(Map<Character, Integer> needs, Map<Character, Integer> window) {
        for (Map.Entry<Character, Integer> needEntity : needs.entrySet()) {
            if (window.getOrDefault(needEntity.getKey(),0) < needEntity.getValue()) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";

        MinWindow minWindow = new MinWindow();
        String s1 = minWindow.minWindow(s, t);
        System.out.println(s1);
    }
}
